Search Results

Documents authored by Chauhan, Ankit


Document
Greed is Good for Deterministic Scale-Free Networks

Authors: Ankit Chauhan, Tobias Friedrich, and Ralf Rothenberger

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)


Abstract
Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real-world networks are not drawn at random. In fact, the behavior of real-world networks and random graph models can be the complete opposite of one another, depending on the considered property. Brach, Cygan, Lacki, and Sankowski [SODA 2016] introduced two natural deterministic conditions: (1) a power-law upper bound on the degree distribution (PLB-U) and (2) power-law neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLB-N). They showed that many real-world networks satisfy both deterministic properties and exploit them to design faster algorithms for a number of classical graph problems like transitive closure, maximum matching, determinant, PageRank, matrix inverse, counting triangles and maximum clique. We complement the work of Brach et al. by showing that some well-studied random graph models exhibit both the mentioned PLB properties and additionally also a power-law lower bound on the degree distribution (PLB-L). All three properties hold with high probability for Chung-Lu Random Graphs and Geometric Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs. As a consequence, all results of Brach et al. also hold with high probability for Chung-Lu Random Graphs and Geometric Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs. In the second part of this work we study three classical NP-hard combinatorial optimization problems on PLB networks. It is known that on general graphs, a greedy algorithm, which chooses nodes in the order of their degree, only achieves an approximation factor of asymptotically at least logarithmic in the maximum degree for Minimum Vertex Cover and Minimum Dominating Set, and an approximation factor of asymptotically at least the maximum degree for Maximum Independent Set. We prove that the PLB-U property suffices such that the greedy approach achieves a constant-factor approximation for all three problems. We also show that all three combinatorial optimization problems are APX-complete, even if all PLB-properties hold. Hence, a PTAS cannot be expected, unless P=NP.

Cite as

Ankit Chauhan, Tobias Friedrich, and Ralf Rothenberger. Greed is Good for Deterministic Scale-Free Networks. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{chauhan_et_al:LIPIcs.FSTTCS.2016.33,
  author =	{Chauhan, Ankit and Friedrich, Tobias and Rothenberger, Ralf},
  title =	{{Greed is Good for Deterministic Scale-Free Networks}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.33},
  URN =		{urn:nbn:de:0030-drops-68682},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.33},
  annote =	{Keywords: random graphs, power-law degree distribution, scale-free networks, PLB networks, approximation algorithms, vertex cover, dominating set, independent s}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail